public class test1 {

    int[] temp ;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        return mergrSort2(nums,0,n-1);
//        return mergrSort1(nums,0,n-1);
    }

    //降序
    public int mergrSort2(int[] nums ,int left,int right){
        //递归出口
        if(left>=right)return 0;

        int ret = 0;
        //先排序两边
        int mid = (right+left)/2;
        ret+=mergrSort2(nums,left,mid);
        ret+=mergrSort2(nums,mid+1,right);
        int cur1 = left,cur2 = mid+1,i=0;
        //计算翻转对
        while (cur1<=mid  ){
            //这里防止数溢出，所以将*2改成/2.0
            while(cur2<=right && nums[cur1]/2.0<=nums[cur2])  cur2++;

            if(cur2>right)  break;

            ret+=right+1-cur2;
            cur1++;
        }
        //指针一定要重置
        cur1 = left;cur2 = mid+1;

        //再合并两个有序数组
        while (cur1<=mid && cur2<=right){
            if(nums[cur1]<nums[cur2])
                temp[i++] = nums[cur2++];
            else
                temp[i++] = nums[cur1++];
        }
        //处理剩余未合并的数组
        while (cur1<=mid)
            temp[i++] = nums[cur1++];
        while (cur2<=right)
            temp[i++] = nums[cur2++];
        //重新赋值给nums数组
        for(int j = left;j<=right;j++)
            nums[j] = temp[j-left];
        return ret;
    }

    //升序
    public int mergrSort1(int[] nums ,int left,int right){
        //递归出口
        if(left>=right)  return 0;

        int ret = 0;
        //先排序两边
        int mid = (right+left)/2;
        ret+=mergrSort2(nums,left,mid);
        ret+=mergrSort2(nums,mid+1,right);
        int cur1 = left,cur2 = mid+1,i=0;
        //计算翻转对
        while (cur2<=right  ){
            while(cur1<=mid && nums[cur1]/2.0<=nums[cur2])  cur1++;

            if(cur1>mid)  break;

            ret+=mid+1-cur1;
            cur2++;
        }
        //指针一定要重置
        cur1 = left;cur2 = mid+1;

        //再合并两个有序数组
        while (cur1<=mid && cur2<=right){
            if(nums[cur1]<nums[cur2])
                temp[i++] = nums[cur1++];
            else
                temp[i++] = nums[cur2++];
        }
        //处理剩余未合并的数组
        while (cur1<=mid){
            temp[i++] = nums[cur1++];
        }
        while (cur2<=right){
            temp[i++] = nums[cur2++];
        }
        //重新赋值给nums数组
        for(int j = left;j<=right;j++){
            nums[j] = temp[j-left];
        }
        return ret;
    }
}
